package leetcode_200;

import java.util.List;

/**
 *@author 周杨
 *WordBreak_139_ 给定一个字典和一个字符串  判断字符串能否被字典里的词分割成句
 *describe:用动归数组记录划分 剪枝优化算法 时间复杂度O(n) 剪枝每次判断词典里最大长度为循环最大长度
 *         核心思想:如果一个字符串能被划分 那么s=s(0,i)+s(i,j)+s(j,k）
 *         每次从数组中读取 是否前面的能被划分  AC 99%
 *2018年6月3日 下午9:30:42
 */
public class WordBreak_139_ {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	public boolean wordBreak(String s, List<String> wordDict) {
        if(s.length()==0)
        	return true;
        int len=s.length();
        boolean judge[]=new boolean[len+1];
        judge[0]=true;
        for (int i = 1; i < len + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (judge[j] && wordDict.contains(s.substring(j, i))) {
                	judge[i] = true;
                    break;
                }
            }
        }
        return judge[len];
    }


}
